//在经典汉诺塔问题中，有 3 根柱子及 N 个不同大小的穿孔圆盘，盘子可以滑入任意一根柱子。一开始，所有盘子自上而下按升序依次套在第一根柱子上(即每一个盘子只
//能放在更大的盘子上面)。移动圆盘时受到以下限制: 
//(1) 每次只能移动一个盘子; 
//(2) 盘子只能从柱子顶端滑出移到下一根柱子; 
//(3) 盘子只能叠在比它大的盘子上。 
//
// 请编写程序，用栈将所有盘子从第一根柱子移到最后一根柱子。 
//
// 你需要原地修改栈。 
//
// 示例1: 
//
//  输入：A = [2, 1, 0], B = [], C = []
// 输出：C = [2, 1, 0]
// 
//
// 示例2: 
//
//  输入：A = [1, 0], B = [], C = []
// 输出：C = [1, 0]
// 
//
// 提示: 
//
// 
// A中盘子的数目不大于14个。 
// 
// Related Topics 递归 
// 👍 35 👎 0

package leetcode.editor.cn;

import java.util.List;

//Java：汉诺塔问题
public class PMianShi0806HanotaLcci {
    public static void main(String[] args) {
        Solution solution = new PMianShi0806HanotaLcci().new Solution();
        // TO TEST
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /*
         *  汉诺塔问题的解决
         * */

        public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
            if (A == null || B == null || C == null) {
                return;
            }
            move(A, B, C, A.size());
        }

        //1. 确定函数需要解决的问题:
        public void move(List<Integer> A, List<Integer> B, List<Integer> C, int n) {
            //2. 递归终止条件
            if (n < 1) {
                return;
            }

            //确定等价关系表达式
            /*
             * 1. 把n-1个盘子 从A借助C移动到B
             * 2. 把最大的盘子从A移动到C
             * 3. 把n-1个盘子从B借助A移动到C
             * */
            move(A, C, B, n - 1);
            Integer num = A.get(A.size() - 1);//获取最后一个最大的元素
            A.remove(num);//remove的时候传入的必须是一个对象
            C.add(num);
            move(B, A, C, n - 1);
        }


    }
//leetcode submit region end(Prohibit modification and deletion)

}
